{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from types import SimpleNamespace\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class HashTable:\n",
    "\n",
    "    ratio_expand = .8\n",
    "    ratio_shrink = .2\n",
    "    min_size = 11\n",
    "\n",
    "    def __init__(self, size=None):\n",
    "        self._size = size or self.min_size\n",
    "        self._buckets = [None] * self._size\n",
    "        self._list = None\n",
    "        self._count = 0\n",
    "\n",
    "    def _entry(self, key):\n",
    "        # get hash and index\n",
    "        idx = hash(key) % self._size\n",
    "\n",
    "        # find entry by key\n",
    "        p, q = self._buckets[idx], None\n",
    "        while p and p.key != key:\n",
    "            p, q = p.next, p\n",
    "\n",
    "        # index, entry, previous entry\n",
    "        return idx, p, q\n",
    "\n",
    "    def _ensure_capacity(self):\n",
    "        fill = self._count / self._size\n",
    "        \n",
    "        # expand or shrink?\n",
    "        if fill > self.ratio_expand:\n",
    "            self._size = self._size * 2 + 1\n",
    "        elif fill < self.ratio_shrink and self._size > self.min_size:\n",
    "            self._size = (self._size - 1) // 2\n",
    "        else:\n",
    "            return\n",
    "\n",
    "        # reallocate buckets\n",
    "        self._buckets = [None] * self._size\n",
    "\n",
    "        # store entries into new buckets\n",
    "        p = self._list\n",
    "        while p:\n",
    "            idx = hash(p.key) % self._size\n",
    "            p.next = self._buckets[idx]\n",
    "            self._buckets[idx] = p\n",
    "            p = p.entry_next\n",
    "\n",
    "    def __len__(self):\n",
    "        return self._count\n",
    "\n",
    "    def __contains__(self, key):\n",
    "        _, p, _ = self._entry(key)\n",
    "        return bool(p)\n",
    "\n",
    "    def __getitem__(self, key):\n",
    "        _, p, _ = self._entry(key)\n",
    "        return p and p.value\n",
    "\n",
    "    def __setitem__(self, key, value):\n",
    "        idx, p, _ = self._entry(key)\n",
    "\n",
    "        # set entry if key was found\n",
    "        if p:\n",
    "            p.value = value\n",
    "            return\n",
    "\n",
    "        # create new entry\n",
    "        p = SimpleNamespace(\n",
    "            key=key,\n",
    "            value=value,\n",
    "            next=self._buckets[idx],\n",
    "            entry_next=self._list,\n",
    "            entry_prev=None\n",
    "        )\n",
    "\n",
    "        # store to bucket\n",
    "        self._buckets[idx] = p\n",
    "\n",
    "        # store to list\n",
    "        if self._list:\n",
    "            self._list.entry_prev = p\n",
    "        self._list = p\n",
    "\n",
    "        # expand\n",
    "        self._count += 1\n",
    "        self._ensure_capacity()\n",
    "\n",
    "    def __delitem__(self, key):\n",
    "        idx, p, q = self._entry(key)\n",
    "\n",
    "        # key not found\n",
    "        if not p:\n",
    "            return\n",
    "\n",
    "        # remove from bucket\n",
    "        if q:\n",
    "            q.next = p.next\n",
    "        else:\n",
    "            self._buckets[idx] = p.next\n",
    "\n",
    "        # remove from list\n",
    "        if p.entry_next:\n",
    "            p.entry_next.entry_prev = p.entry_prev\n",
    "        if p.entry_prev:\n",
    "            p.entry_prev.entry_next = p.entry_next\n",
    "        else:\n",
    "            self._list = p.entry_next\n",
    "\n",
    "        # shrink\n",
    "        self._count -= 1\n",
    "        self._ensure_capacity()\n",
    "\n",
    "    def __iter__(self):\n",
    "        p = self._list\n",
    "        while p:\n",
    "            yield p.key\n",
    "            p = p.entry_next\n",
    "            \n",
    "    def slots(self):\n",
    "        return ''.join(p and 'x' or '-' for p in self._buckets)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "table = HashTable()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# add random values\n",
    "for _ in range(1000):\n",
    "    key, value = np.random.randint(1000), np.random.rand()\n",
    "    table[key] = value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(625, 1535)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(table), table._size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'-x-x-x-xx-xxxxx-xxx-xxxx-x-x-x---xx-xxx---xx-x--x-xx-x-xxxx-xx-xx--xxx--xx-x-x-xx-x-xxxx-x-xxxx--xxxxx-x--xxx-xxx-xxxxxx--xxxx-xxxxx---xxxxxx--xxxxxxx--xx-x-xx--xx-xxxxx-x-xxxxx-xx--x--xxx-xxxx-x-xx-x---x-xx---xx--xxxxx--xx-x---x--xx-----xxx--x--xx-xx--xxxx-xx---xxxx-x-xxx--x-xxx--xx-xx-xx-xx--xx-xx-xxxxxx-xxxxxx--xx-x-xx---xx--x-xxx--xx-xx-x-xx-x-x-xxxx--xx-xx-x-xx-x--xxx-xx---xx--xx--x-xxx---x-xxxxxxx--xxx-x---x-x-x--x-xxxxx---x-xxxxx----xx-xxxx-x-xxxxxxxxx-xxxxxx---xx-x--xx-xx-xxx--xxx-x---xxxxx--x-xx-xx---xxx-xx--xx-xx-xx-xx-xxxxx--xx-xxx-x----x-xxxx--xxxx-xxxxxx--xxxxxx-x-x-x--x-xxx--xx-x-x-x-xxxx-xx-x-x-x-xxx--xxxxxx-xxxxxxx-x-x-xxxxxxx-xxx-xxx-x-xxx-xxxxx---x-xxxx-x-x-x--x---xxx--xxxx-xxxx----xxxx-xxx-xxx-xx-x-x-xxx-x---xxx-xx-x--x-xx--xxx-x-xxxxxx-xxx--xx----x-xxxxxxx-------x-x-xxxxxxx-x-x-x-----xxxxx-xxxxx--xxx-xxx-----xxx-xxxx--xxxxxxx--xx-xxx-xx---xx-xxxxxxxxxxxxxx-xxxx--x--x--xxxx---xxxxxx-xxxx---xxx---x-xxxxxx-x--xxxx--xxxxx---xxx-x-x---xxx---xx-xx-x-xxxx--xxx-xxxxxx--xx-x-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "table.slots()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "918 0.46964946620099624\n",
      "880 0.6586348500634474\n",
      "633 0.06134674099379567\n",
      "89 0.7216673947800543\n",
      "53 0.7986314320745663\n"
     ]
    }
   ],
   "source": [
    "# print some values\n",
    "for key in list(table)[:5]:\n",
    "    print(key, table[key])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# delete all the values\n",
    "for key in list(table):\n",
    "    del table[key]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 11)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(table), table._size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
